package lab8;
/*
 * Bai1
 * @author: nguyentrongtri
 * @created date: 2014/06/07
 */

public class LinkedList<T extends Comparable<T>> implements List<T> {
    private Node<T> head;

    public LinkedList() {
        this.head = null;
    }

    @Override
    public void addFirst(T item) {
        Node<T> node = new Node<T>(item, head);
        head = node;
    }

    @Override
    public void addLast(T item) {
        if (head == null)
            addFirst(item);
        else {
            Node<T> current = head;
            while (current.getNext() != null) {
                current = current.getNext();
            }
            Node<T> newNode = new Node<T>(item, null);
            current.setNext(newNode);
        }
    }

    @Override
    public void insertAfter(T key, T item) {
        Node<T> tmp = head;
        while (tmp != null) {
            if (tmp.getData().compareTo(key) == 0) {
                tmp.setNext(new Node<T>(item, tmp.getNext()));
                return;
            }
            tmp = tmp.getNext();
        }
    }

    @Override
    public void insertBefore(T key, T item) {
        if (head == null)
            return;
        if (head.getData().compareTo(key) == 0) {
            addFirst(item);
            return;
        }
        Node<T> previous = null;
        Node<T> current = head;
        while (current != null) {
            if (current.getData().compareTo(key) == 0)
                break;
            previous = current;
            current = current.getNext();
        }
        previous.setNext(new Node<T>(item, current));
    }

    @Override
    public void remove(T key) {
        if (head == null)
            return;
        if (head.getData().compareTo(key) == 0) {
            removeFirst();
            return;
        }
        Node<T> previous = head;
        Node<T> current = head;
        while (current != null) {
            if (current.getData().compareTo(key) == 0) {
                previous.setNext(current.getNext());
                return;
            }
            previous = current;
            current = current.getNext();
        }
    }

    @Override
    public void removeFirst() {
        if (head == null)
            return;
        head = head.getNext();
    }

    @Override
    public void removeLast() {
        if (head == null)
            return;
        if (head.getNext() == null)
            head = null;
        Node<T> previous = head;
        Node<T> current = head;
        while (current.getNext() != null) {
            previous = current;
            current = current.getNext();
        }
        previous.setNext(null);
    }

    @Override
    public String toString() {
        String s = "";
        s += "[";
        Node<T> current = head;
        while (current != null) {
            s += current.getData().toString() + ", ";
            current = current.getNext();
        }
        if (s.length() > 2)
            s = s.substring(0, s.length() - 2);
        s += "]";
        return s;
    }

}
